/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

//n次循环，每次循环合并一个链表
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode res = null;
        for(int i = 0; i < lists.length; i++){
          res = merge(res, lists[i]);
        }
        return res;
    }
    public ListNode merge(ListNode list1, ListNode list2){
        if(list1 == null || list2 == null){
            return list1 != null ? list1 : list2;
        }
        ListNode head = new ListNode(-1);
        ListNode tail = head;
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                tail.next = list1;
                list1 = list1.next;
            }else{
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }
        tail.next = (list1 != null ? list1 : list2);
        return head.next; 
    }
}
//采用分治思想优化，对数组两两归并，最后合成一个链表
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }
    public ListNode merge(ListNode[] lists, int left, int right){
        if(left == right){
            return lists[left];
        }
        if(left > right){
            return null;
        }
        int mid = (left + right) >> 1;
        return mergeLists(merge(lists, left, mid), merge(lists, mid + 1, right));
    }

    public ListNode mergeLists(ListNode list1, ListNode list2){
        if(list1 == null || list2 == null){
            return list1 != null ? list1 : list2;
        }
        ListNode head = new ListNode(-1);
        ListNode tail = head;
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                tail.next = list1;
                list1 = list1.next;
            }else{
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }
        tail.next = (list1 != null ? list1 : list2);
        return head.next; 
    }
}
//采用优先队列，每次取全部数组中的最小值加入链表
class Solution {
    class Status implements Comparable<Status> {
        int val;
        ListNode ptr;

        Status(int val, ListNode ptr) {
            this.val = val;
            this.ptr = ptr;
        }

        public int compareTo(Status status2) {
            return this.val - status2.val;
        }
    }

    PriorityQueue<Status> queue = new PriorityQueue<Status>();

    public ListNode mergeKLists(ListNode[] lists) {
        for (ListNode node: lists) {
            if (node != null) {
                queue.offer(new Status(node.val, node));
            }
        }
        ListNode head = new ListNode(0);
        ListNode tail = head;
        while (!queue.isEmpty()) {
            Status f = queue.poll();
            tail.next = f.ptr;
            tail = tail.next;
            if (f.ptr.next != null) {
                queue.offer(new Status(f.ptr.next.val, f.ptr.next));
            }
        }
        return head.next;
    }
}